package puzzle.projecteuler.p200;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.net.URL;
import java.net.URLDecoder;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import astudy.util.Combination;

public class Problem105C {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws IOException {
		
		List<Integer[]> datas = readData();
		Long sum = 0L;
		for (Integer[] array: datas) {
			if (check(array)) {
				sum += sum(array);
			}
		}
		System.out.println(sum);
	}

	public static List<Integer[]> readData() throws IOException {

		URL url = Problem105C.class.getResource("Problem105.txt");
		File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));

		List<Integer[]> datas = new ArrayList<Integer[]>();
		BufferedReader br = new BufferedReader(new FileReader(file));
		String line = null;
		while ((line = br.readLine()) != null) {
			String[] tmp = line.split(",");
			Integer[] iarray = new Integer[tmp.length];
			for (int c = 0; c < iarray.length; c ++) {
				iarray[c] = Integer.valueOf(tmp[c]);
			}
			datas.add(iarray);
		}
		br.close();
		return datas;
	}
	
	/**
	 * 测试指定的集合是否满足条件 
	 * @param array
	 * @return
	 */
	private static boolean check(Integer[] array) {

		int[] indexes = new int[array.length];
		for (Integer i = 0; i < indexes.length; i ++) {
			indexes[i] = 0;
		}
		int[] minArray = new int[array.length];	//记录每种长度的集合,和的最小值
		minArray[0] = 0;
		int[] maxArray = new int[array.length];	//记录每种长度的集合,和的最大值
		maxArray[0] = 0;
		for (int i = 0; i < array.length; i ++) {
			minArray[i] = -1;
			maxArray[i] = -1;
		}
		Set<Integer> sums = new HashSet<Integer>();	//记录所有的集合和
		while ((indexes = Combination.next(array.length+1, indexes)) != null) {
			Integer[] tmp = new Integer[indexes.length];
			int count = 0;
			for (Integer i = 0; i < tmp.length; i++) {
				if (indexes[i] == 0) {
					tmp[i] = null;
				} else {
					count ++;
					tmp[i] = array[indexes[i]-1];
				}
			}
			Integer sum = sum(tmp);
			if (sums.contains(sum)) {
				return false;
			} else {
				sums.add(sum);
				if (maxArray[count-1] == -1 || sum > maxArray[count-1]) {
					maxArray[count-1] = sum;
				}
				if (minArray[count-1] == -1 || sum < minArray[count-1]) {
					minArray[count-1] = sum;
				}
			}
		}
		for (int i = 1; i < array.length-1; i ++) {
			if (maxArray[i] >= minArray[i+1]) {
				return false;
			}
		}
		return true;
	}
	
	private static Integer sum(Integer[] a) {
		
		Integer s = 0;
		for (Integer i = 0; i < a.length; i ++) {
			if (a[i] != null) {
				s += a[i];
			}
		}
		return s;
	}
}
